package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * http://www.leetcode.com/onlinejudge
 * 
 * Decode Ways
 * 
 * @author yunzhang
 *
 */
public class DecodingWays {
	private Map<String, String> map;

	public DecodingWays() {
		map = new HashMap<String, String>();

		map.put("1", "A");
		map.put("2", "B");
		map.put("3", "C");
		map.put("4", "D");
		map.put("5", "E");
		map.put("6", "F");
		map.put("7", "G");
		map.put("8", "H");
		map.put("9", "I");
		map.put("10", "J");
		map.put("11", "K");
		map.put("12", "L");
		map.put("13", "M");
		map.put("14", "N");
		map.put("15", "O");
		map.put("16", "P");
		map.put("17", "Q");
		map.put("18", "R");
		map.put("19", "S");
		map.put("20", "T");
		map.put("21", "U");
		map.put("22", "V");
		map.put("23", "W");
		map.put("24", "X");
		map.put("25", "Y");
		map.put("26", "Z");
	}

	public int numDecodings(String s) {

		List<String> all = allDecodings(s);

		return all.size();
	}

	public List<String> allDecodings(String s) {
		if (s.isEmpty()) {
			return new ArrayList<String>();
		}

		String first = s.substring(0, 1);

		String ch = map.get(first);
		if (ch != null) {
			List<String> subDecodings = allDecodings(s.substring(1));
			if (subDecodings.size() == 0){
				if (s.substring(1).isEmpty())
					subDecodings.add(map.get(ch));
			}
			else {
				for (String decoding : subDecodings) {
					decoding = ch + decoding;
				}
			}

			if (s.length() > 1) {
				String firstTwo = s.substring(0, 2);

				if (map.containsKey(firstTwo)) {
					List<String> sds = allDecodings(s.substring(2));

					if (sds.size() == 0){
						if (s.substring(2).isEmpty())
							subDecodings.add(map.get(ch));
					}
					else {
						for (String decoding : sds) {
							decoding = ch + decoding;
						}
					}

					subDecodings.addAll(sds);
				}
			}
			return subDecodings;
		} else {
			return new ArrayList<String>();
		}
	}
	
	int decodeways(String s){
		char [] chs = s.toCharArray();

		if (chs.length == 0)
			return 0;
		if (chs.length == 1)
			return isValidSingle(chs[0]) ? 1:0;
		if (chs.length == 2)
			return (isValidSingle(chs[0]) && isValidSingle(chs[1]) ? 1:0) +
				(isValid(chs[0], chs[1]) ? 1 : 0);

		int[] nways = new int[3];

		if (isValidSingle(chs[0]))
			nways[0] = 1;
		else
			return 0;

		nways[1] = (isValidSingle(chs[0]) && isValidSingle(chs[1]) ? 1:0) +
				(isValid(chs[0], chs[1]) ? 1 : 0);

		if (nways[1] == 0)
			return 0;

		for (int p=2; p<chs.length; ++p){
			if (chs[p] == '0'){
				if (isValid(chs[p-1], chs[p]))
					nways[p%3] = nways[(p-2)%3];
				else
					return 0; 
			} else if (isValidSingle(chs[p])){
				if (isValid(chs[p-1], chs[p]))
					nways[p%3] = nways[(p-1)%3]	+ nways[(p-2)%3];
				else
					nways[p%3] = nways[(p-1)%3];
			} else{
				return 0;
			}
		}

		return nways[(chs.length-1)%3];
	}

	boolean isValidSingle(char c){
		return c >='1' && c<='9' ? true: false;
	}

	boolean isValid(char c1, char c2){
		if (c1 == '1')
			return c2 >='0' && c2<='9'? true: false;
		else if (c1 == '2')
			return c2 >= '0' && c2 <= '6' ? true: false;
		else
			return false;
	}

	public static void main(String[] args) {
		DecodingWays dw = new DecodingWays();
		System.out.println(dw.numDecodings("12"));
	}
}
